package letcode.oneQuestionPerDay._202003._20200320;

/*
最小的k个数
    官方题解：快速排序
 */
public class LittlestKNumber_1 {
    public static void main(String[] args) {
        int[] arr={3,2,1,2,3,4,0,1};
        int k=6;
        int[] newArr=getLeastNumbers(arr,k);
        for (int i:newArr
             ) {
            System.out.println(i);
        }

    }
    public static int[] getLeastNumbers(int[] arr, int k) {
        //边界情况考虑
        if (k==0){
            return new int[0];
        }else if (arr.length<=k){
            return arr;
        }

        //划分数组
        partitionArray(arr,0,arr.length-1,k);

        //取前k个数，输出
        int[] res=new int[k];
        for (int i = 0; i < k; i++) {
            res[i]=arr[i];
        }
        return res;
    }

    //切割操作
    public static void partitionArray(int[] arr,int lo,int hi,int k){
        //做一次prition操作
        int m=partition(arr,lo,hi);
        //此时数组前m个数，就是最小的m个数
        if (k==m) //正好找到
            return;
        else if (k<m)  //最小的k个数一定在前m个数中，递归划分
            partitionArray(arr,lo,m-1,k);
        else//在右侧数组寻找最小的k
            partitionArray(arr,m+1,hi,k);
    }
    //一次划分操作
    //思想：把第一个数，当作划分点，左边和右边开始，如果左边找到一个比m大的，右边找到一个比m小的，两个交换位置。如果左边的指针大于右边的指针则结束。最后把第一位
    public static int partition(int[] a,int lo,int hi){
        //定义变量
        int i=lo; //从左向右
        int j=hi+1; //从右向左
        int v=a[lo];

        //遍历划分
        while (true){
            while (a[++i]<v){
                if (i==hi)
                    break;
            }
            while (a[--j]>v){
                if (j==lo)
                    break;
            }

            if (i>=j)
                break;

            swap(a,i,j);
        }
        swap(a,lo,j);

        return j;
    }
    //划分所需要的交换操作
    public static void swap(int[] a,int i,int j){
        int temp=a[j];
        a[j]=a[i];
        a[i]=temp;
    }
}
/*
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。


示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]
 */